/*
    区间dp-上

    前置知识: 
    讲解067、讲解068 - 从递归入手二维动态规划 & 空间压缩技巧
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

    区间dp：大范围的问题拆分成若干小范围的问题来求解

    可能性展开的常见方式：
    1）基于两侧端点讨论的可能性展开
    2）基于范围上划分点的可能性展开

    区间dp专题分为上、下两期，一共12个题
    本节课 区间dp-上 会安排6个题，熟悉区间dp的可能性展开

    注意：尤其是 讲解067 - 从递归入手二维动态规划，整个套路请务必掌握！

    ================================================

    题目1
    让字符串成为回文串的最少插入次数
    给你一个字符串 s
    每一次操作你都可以在字符串的任意位置插入任意字符
    请你返回让s成为回文串的最少操作次数
    测试链接 : https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/


    注意：
    本题有关空间压缩的实现，可以参考讲解067，题目4，最长回文子序列问题的讲解
    这两个题空间压缩写法高度相似
    因为之前的课多次讲过空间压缩的内容，所以这里不再赘述

    ================================================

    题目2
    预测赢家
    给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏
    玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手
    开始时，两个玩家的初始分值都是 0
    每一回合，玩家从数组的任意一端取一个数字
    取到的数字将会从数组中移除，数组长度减1
    玩家选中的数字将会加到他的得分上
    当数组中没有剩余数字可取时游戏结束
    如果玩家 1 能成为赢家，返回 true
    如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true
    你可以假设每个玩家的玩法都会使他的分数最大化
    测试链接 : https://leetcode.cn/problems/predict-the-winner/

    ================================================

    题目3
    多边形三角剖分的最低得分
    你有一个凸的 n 边形，其每个顶点都有一个整数值
    给定一个整数数组values，其中values[i]是第i个顶点的值(顺时针顺序)
    假设将多边形 剖分 为 n - 2 个三角形
    对于每个三角形，该三角形的值是顶点标记的乘积
    三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和
    返回 多边形进行三角剖分后可以得到的最低分
    测试链接 : https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/

    ================================================

    题目4
    切棍子的最小成本
    有一根长度为n个单位的木棍，棍上从0到n标记了若干位置
    给你一个整数数组cuts，其中cuts[i]表示你需要将棍子切开的位置
    你可以按顺序完成切割，也可以根据需要更改切割的顺序
    每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和
    对棍子进行切割将会把一根木棍分成两根较小的木棍
    这两根木棍的长度和就是切割前木棍的长度
    返回切棍子的最小总成本
    测试链接 : https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/

    ================================================

    题目5
    戳气球
    有 n 个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中
    现在要求你戳破所有的气球。戳破第 i 个气球
    你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币
    这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号
    如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球
    求所能获得硬币的最大数量
    测试链接 : https://leetcode.cn/problems/burst-balloons/

    ================================================

    题目6
    布尔运算
    给定一个布尔表达式和一个期望的布尔结果 result
    布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成
    布尔表达式一定是正确的，不需要检查有效性
    但是其中没有任何括号来表示优先级
    你可以随意添加括号来改变逻辑优先级
    目的是让表达式能够最终得出result的结果
    返回最终得出result有多少种不同的逻辑计算顺序
    测试链接 : https://leetcode.cn/problems/boolean-evaluation-lcci/

*/